package com.job.tencent;

import java.util.*;

/**
 * @ClassName: Tencent4
 * @Description:
 * @Author: 12071
 * @Date: 2022/4/24 21:14
 */
public class Tencent4 {
    public static void main(String[] args) {
        ListNode[] input = new ListNode[]{
                new ListNode(new int[]{1,2,3}),
                new ListNode(new int[]{3,4,1}),
                new ListNode(new int[]{2,3,4})
        };
        solve(input);

    }



    public static ListNode solve(ListNode[] a) {
        Map<Integer,ListNode> headMap = new HashMap<>();
        // write code here
        for (ListNode head : a) {
            headMap.put(head.val,head);
        }
        List<Integer> list = new ArrayList<>();
        ListNode top = a[0];
        list.add(top.val);
        ListNode node;
        if(headMap.containsKey(top.val)){
            top.next = headMap.get(top.val).next;
        }
        node = top.next;
        ListNode minNode = top;
        while(node.val!=top.val){
            list.add(node.val);
            if(headMap.containsKey(node.val)){
                node.next = headMap.get(node.val).next;
            }
            if(node.val < top.val) minNode = node;
            node = node.next;
            System.out.println(node.val);
        }
        while (node.next.val==minNode.val){
            top = node.next;
            node.next = null;
        }
        System.out.println(list);
        // 此时已经得到了最终的链表（以列表表示，顺时针）以及最小值和它的位置
        // 之后需要判断其左右两边的元素大小来决定顺时针还是逆时针输出
        // 根据决定好的顺序重新构造链表
        return top;
    }




    static class ListNode {
        int val;
        ListNode next = null;

        public ListNode(int val) {
            this.val = val;
        }

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }

        public ListNode(int[] arr){
            ListNode tmp = null;
            for (int i = arr.length-1; i >0; i--) {
                tmp = new ListNode(arr[i],tmp);
            }
            this.val = arr[0];
            this.next = tmp;
        }

        @Override
        public String toString() {
            List<Integer> list = new ArrayList();
            ListNode node = this;
            while (node!=null){
                list.add(node.val);
                node = node.next;
            }
            return list.toString();
        }
    }
}
